Many problems in mobile communications can be described with a simple linear multiple-input multiple-output (MIMO) model. Examples include multiantenna systems or multiuser detection in CDMA. The transmission characteristics of such systems can usually be modeled, at least in approximation, by the equationy=Hs+n,  (1)wherein    y is an N×1 vector describing a received signal,    H is a channel matrix, wherein H=QR with an M×M upper triangular matrix R and an N×M unitary matrix Q,    s a transmitted M×1 signal vector whose coordinate values are chosen from a constellation O containing A possible coordinate values,    n is a N×1 vector of proper independently, identically distributed zero-mean complex Gaussian noise entries,    M is a number of transmitter sources, and    N is a number of receiver sinks.
The coordinates siεO of the symbols s are composed of values chosen from the complex constellation O. Real constellations can be considered as a special case. A typical solution of (1) for maximum likelihood (ML) detection involves the computation of
                              s          ^                =                              argmin                          s              ∈              O                                ⁢                                                                  Rs                -                                  y                  ^                                                                    2                                              (        2        )            with ∥ ∥2 denoting the Euclidean l2-norm and with ŷ=QHy, and with QH being the conjugate transpose of Q. Other mathematically equivalent methods may be used as well to arrive at an expression similar to (2).
In other words, the vectors s are transformed (via a unitary matrix Q) into a space where matrix R is triangular because, as described below, a triangular matrix R allows an efficient implementation of a recursive search algorithm. A transformation via a unitary matrix Q leaves the traditional l2-norm of the trans-formed vectors unchanged, and therefore (2) is equivalent to a minimization of the Euclidean distance between Hs and y.
In fading MIMO channels, ML detection exploits Nth order diversity, which is not achieved by linear and successive cancellation receivers. Hence, ML detection is attractive in the high SNR regime. Unfortunately, the complexity of an exhaustive search implementation of (2) is exponential in the transmission rate. For the case where OM is a (real) integer lattice LM, sphere decoding (SD) has been proposed by Pohst [1] as an alternative approach, which has recently been introduced into communications. The algorithm achieves ML performance with an expected complexity that grows only polynomial in the rate [7]. Numerous optimizations have been proposed to reduce the implementation complexity of the original SD algorithm on general purpose processors and digital signal processors (DSPs) [3]. However, the VLSI implementation of the algorithm has only received limited attention so far.